package leetcode;

import java.util.Arrays;

public class Leetcode877 {
    public boolean stoneGame(int[] piles) {
        int[][] mem = new int[piles.length][piles.length];
        for (int i = 0; i < mem.length; i++) {
            Arrays.fill(mem[i],Integer.MIN_VALUE);
            mem[i][i] = piles[i];
        }
        return dfs(piles,0,piles.length-1,mem)>=0;
    }

    public int dfs(int[] piles,int left,int right,int[][] mem){
        if(left>right){
            return 0;
        }
        if(mem[left][right]!=Integer.MIN_VALUE){
            return mem[left][right];
        }
        int selectLeft = piles[left]-dfs(piles,left+1,right,mem);
        int selectRight = piles[right]-dfs(piles,left,right-1,mem);
        return mem[left][right] = Math.max(selectLeft,selectRight);
    }
}
